﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace pintu
{
    class Program
    {
      


        
      
        static void Main(string[] args)
        {
            int[] start = new int[9];
            int[] target = new int[9] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            int yansuanbuzhou = 21;
            Console.WriteLine("输入待拼图的最大步骤（建议设置21）)：");
            while (true)
            {
                string inputstr = Console.ReadLine();
             
                try
                {

                    yansuanbuzhou = System.Convert.ToInt32(inputstr);
                    if (yansuanbuzhou > 10 && yansuanbuzhou < 50)
                        break;
                    else
                        throw new Exception();

             
                }
                catch
                {
                    Console.WriteLine("检查输入格式重新输入:");
                }



            }
            Console.WriteLine("输入待拼图的排列顺序以小数点隔开：");
            while (true)
            {
                string inputstr = Console.ReadLine();
                string[] arr = inputstr.Split('.');
                try
                {
                    if (arr.Length != 9) throw new Exception();
                    for (int i = 0; i < arr.Length; i++)
                    {
                        start[i] = System.Convert.ToInt32(arr[i]);

                    }
                    break;
                }
                catch
                {
                    Console.WriteLine("检查输入格式重新输入:");
                }
       


            }
    


            int kongbaidindex = -1;
            for (int i = 0; i < start.Length; i++)
            {
                if (start[i] == 9)
                    kongbaidindex = i;


            }

            Pintu pintu = new Pintu(start, target, yansuanbuzhou);
            pintu.getlujing((kongbaidindex+1).ToString(), yansuanbuzhou);







        }



     
    }



    class Pintu
    {
        int[] start;
        int[] target;

        int yansuanbuzhou;

      public  Pintu(int[] start,int[] target,int yansuanbuzhou)
        {
            this.start = start;
            this.target = target;
            this.yansuanbuzhou = yansuanbuzhou;

        }

        public  bool checklujing(List<string> lujing, out List<string> resout)
        {
            int[] tempstart;
            tempstart = (int[])start.Clone();
            int[] temptarget;
            temptarget = (int[])target.Clone();

            List<string> res = new List<string>();

            int buzhouindex = 0;
            foreach (var buzhou in lujing)
            {
                buzhouindex++;
                if (buzhouindex == lujing.Count) break;



                int kongbaidindex = -1;
                for (int i = 0; i < tempstart.Length; i++)
                {
                    if (tempstart[i] == 9)
                    {
                        kongbaidindex = i;
                        break;
                    }
                }
                int newkonggeindex = -1;
                int temp = -1;
                switch (buzhou)
                {
                    case "上":
                         newkonggeindex = kongbaidindex - 3;
                         temp = tempstart[newkonggeindex];
                        tempstart[newkonggeindex] = 9;
                        tempstart[kongbaidindex] = temp;
                      
                        break;
                    case "下":
                         newkonggeindex = kongbaidindex + 3;
                         temp = tempstart[newkonggeindex];
                        tempstart[newkonggeindex] = 9;
                        tempstart[kongbaidindex] = temp;
                        break;
                    case "左":
                        newkonggeindex = kongbaidindex - 1;
                        temp = tempstart[newkonggeindex];
                        tempstart[newkonggeindex] = 9;
                        tempstart[kongbaidindex] = temp;
                        break;
                    case "右":
                        newkonggeindex = kongbaidindex + 1;
                        temp = tempstart[newkonggeindex];
                        tempstart[newkonggeindex] = 9;
                        tempstart[kongbaidindex] = temp;
                        break;
                    default:
                        break;
                }
                kongbaidindex = newkonggeindex;
                //for (int i = 0; i < tempstart.Length; i++)
                //{
                //    Console.Write(tempstart[i]+",");
                //}
                //Console.WriteLine();
                res.Add(buzhou);
                if (Enumerable.SequenceEqual(tempstart, temptarget))
                {
                    resout = res;
                    return true;


                }
                  


            }
            resout = null;
            return false;






        }



        List<string> getcanmovefangxiang(string kongweizhi)
        {
            switch (kongweizhi)
            {
                case "1":return new List<string>() { "右", "下" };   
                case "2":return new List<string>() { "左", "右", "下" };
                case "3": return new List<string>() { "左", "下" };
                case "4": return new List<string>() { "上", "下", "右"};
                case "5": return new List<string>() { "上", "下", "右", "左" };
                case "6": return new List<string>() { "上", "下", "左" };
                case "7": return new List<string>() { "右", "上" };
                case "8": return new List<string>() { "左", "右", "上" };
                case "9": return new List<string>() { "左", "上" };
                default:
                    return new List<string>() { };
            }
        }

         List<string> createlujing(List<string> lastlujing,string fangxiang)
        {
            string newkongweizhi = "";
            switch (lastlujing[lastlujing.Count-1])
            {
                case "1":
                    switch (fangxiang)
                    {
                        case "右":
                            newkongweizhi = "2";break;
                        case "下":
                            newkongweizhi = "4"; break;

                    }break;


                case "2":
                    switch (fangxiang)
                    {
                        case "右":
                            newkongweizhi = "3"; break;
                        case "下":
                            newkongweizhi = "5"; break;
                        case "左":
                            newkongweizhi = "1"; break;

                    }
                    break;
                case "3":
                    switch (fangxiang)
                    {


                        case "下":
                            newkongweizhi = "6"; break;
                        case "左":
                            newkongweizhi = "2"; break;


                    }
                    break;
                case "4":
                    switch (fangxiang)
                    {
                        case "右":
                            newkongweizhi = "5"; break;
                        case "下":
                            newkongweizhi = "7"; break;

                        case "上":
                            newkongweizhi = "1"; break;

                    }
                    break;
                case "5":
                    switch (fangxiang)
                    {
                        case "右":
                            newkongweizhi = "6"; break;
                        case "下":
                            newkongweizhi = "8"; break;
                        case "左":
                            newkongweizhi = "4"; break;
                        case "上":
                            newkongweizhi = "2"; break;

                    }
                    break;
                case "6":
                    switch (fangxiang)
                    {
                        case "下":
                            newkongweizhi = "9"; break;
                        case "左":
                            newkongweizhi = "5"; break;
                        case "上":
                            newkongweizhi = "3"; break;

                    }
                    break;
                case "7":
                    switch (fangxiang)
                    {
                        case "右":
                            newkongweizhi = "8"; break;
                        case "上":
                            newkongweizhi = "4"; break;

                    }
                    break;
                case "8":
                    switch (fangxiang)
                    {
                        case "右":
                            newkongweizhi = "9"; break;
                        case "左":
                            newkongweizhi = "7"; break;
                        case "上":
                            newkongweizhi = "5"; break;

                    }
                    break;
                case "9":
                    switch (fangxiang)
                    {

                        case "左":
                            newkongweizhi = "8"; break;
                        case "上":
                            newkongweizhi = "6"; break;

                    }
                    break;
                default:
                    break;
            }

            List<string> res = new List<string>();
            for (int i = 0; i < lastlujing.Count-1; i++)
            {
                res.Add(lastlujing[i]);
            }
            res.Add(fangxiang);
            res.Add(newkongweizhi);
            return res;
        }

        public List<string> getlujing(string kongweizhi,int bushu)
        {

            List<List<string>> lujings = new List<List<string>>();
            List<string> lujing = new List<string>{ kongweizhi };//9

          


            lujings.Add(lujing);
            for (int i = 0; i < bushu; i++)
            {
                Console.Write("当前步数;" + i);
                List<List<string>> newlujings = new List<List<string>>();
                foreach (var item in lujings)
                {
                    string newkongweizhi = item[item.Count - 1];
                    List<string> Canmovefangxaing = getcanmovefangxiang(newkongweizhi);
                    foreach (var item2 in Canmovefangxaing)
                    {

                        if (item.Count >= 2)
                        {
                            string lastfangxaing = item[item.Count - 2];
                            if ((lastfangxaing == "左" && item2 == "右") || (lastfangxaing == "右" && item2 == "左") || (lastfangxaing == "上" && item2 == "下") || (lastfangxaing == "下" && item2 == "上"))
                            {
                                continue;
                            }

                        }



                        List<string> newlujing = createlujing(item, item2);
                        List<string> resout = new List<string>();
                        if (checklujing(newlujing, out resout))
                        {
                            Console.WriteLine("步数： "+resout.Count);
                            foreach (var item__ in resout)
                            {
                                Console.Write(item__ + ",");
                            }

                            return resout;
                        }
                           


                        newlujings.Add(newlujing);
                    
                    }
                  
                   
                }

                lujings = new List<List<string>>(newlujings);
                Console.WriteLine("------------------Completed");

            }
            //foreach (var item in lujings)
            //{
            //    foreach (var item_ in item)
            //    {
            //        Console.Write(item_ + ',');
            //    }
            //    Console.WriteLine();
            //}
            return null;

        }


    }


}
